package com.leetcode.LeetCode精选TOP面试题;

/**
 * @author 覃国强
 * @date 2022-05-19 19:06
 */
public class 题库_0028_实现strStr {

  static
  class Solution {
    public int strStr(String haystack, String needle) {
      if (haystack == null || needle == null) {
        return -1;
      }
      if (needle.length() == 0) {
        return 0;
      }
      int[] pi = new int[needle.length()];
      for (int i = 1, j = 0; i < needle.length(); ++i) {
        while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
          j = pi[j - 1];
        }
        if (needle.charAt(i) == needle.charAt(j)) {
          j++;
        }
        pi[i] = j;
      }

      for (int i = 0, j = 0; i < haystack.length(); ++i) {
        while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
          j = pi[j - 1];
        }
        if (haystack.charAt(i) == needle.charAt(j)) {
          j++;
        }
        if (j == needle.length()) {
          return i - needle.length() + 1;
        }
      }

      return -1;
    }
  }

}
